// 思路：利用堆结构，将数组转为大顶堆，重复让头部元素和尾部元素交换位置，让除了尾部元素的剩余元素继续维持大顶堆

function maxHeapSort(arr) {
    // 1. 构造大顶堆
    buildMaxHeap(arr)
    // 2. 交换首尾并重新heapify
    for (let i = 0; i < arr.length; i++) {
        [arr[0], arr[arr.length - 1 - i]] =  [arr[arr.length - 1 - i], arr[0]];    
        heapify(arr, 0, arr.length - 2 - i)  
    }
    return arr
}

function buildMaxHeap(arr) {
     // 从最后一个父节点开始向上调整，(这样自底向上效率更高),直到根节点，最后一个父节点的索引是 Math.floor((arr.length - 1) / 2)
     for (let i = Math.floor((arr.length - 1) / 2); i >=0; i--) {
        heapify(arr, i, arr.length - 1)        
    }
}

function heapify(arr, start, end) {
    // 父节点为index，左节点为 2 * index + 1， 右节点为 2 * index + 2
    let leftIndex = 2 * start + 1
    let rightIndex = leftIndex + 1
    while (leftIndex <= end) {
        let maxIndex = start
        if (arr[leftIndex] > arr[maxIndex]) {
            maxIndex = leftIndex
        }
        if (rightIndex <= end && arr[rightIndex] > arr[maxIndex]) {
            maxIndex = rightIndex
        }
        // 如果小于父节点值，那直接退出循环，因为子节点的值已经比较过了
        if (maxIndex === start) {
            break
        }
        [arr[start], arr[maxIndex]] = [arr[maxIndex], arr[start]];
        start = maxIndex
        leftIndex = 2 * start + 1
        rightIndex = leftIndex + 1
    }
}

// 时间复杂度 Onlogn
// 空间复杂度 O1
// 不稳定排序

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(maxHeapSort(arr))